package interview.Datastructures;

class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	public TreeNode(int num) {
		data=num;
		left=null;
		right=null;
	}	
}


class Tree{
	private TreeNode root;
	public void insert(int num){
		TreeNode newNode = new TreeNode(num);
		if (root==null) root = newNode;
		else insertRecur(num,root);		
	}
	private void insertRecur(int num, TreeNode current) {
		if(current.data>=num){
			if(current.left != null)
				insertRecur(num, current.left);
			else
				current.left=new TreeNode(num);
		}
		else{
			if(current.right != null)
				insertRecur(num, current.right);
			else
				current.right=new TreeNode(num);
		}
	}
	
	public TreeNode findMin(TreeNode current){
		if (current.left==null) return current;
		else{
			while(current.left!=null)
				current =current.left;
			return current;
		}
	}
	
	public void delete(int num){
		if (root==null) return;
		else deleteRecur(num,root);
	}
	
	private void deleteRecur(int num, TreeNode current) {
		boolean flag;		
		if(current==null) return;
		TreeNode parent, child;
		while(true){
			if(current.data>num){
				if(current.left==null) return;
				else if(current.left.data == num) break;
				else current = current.left;
			}
			else if(current.data<num){
				if(current.right==null) return;
				else if(current.right.data == num) break;
				else current = current.right;
			}
			else
				break;			
		}
		if(current.data == num){
			System.out.println("Root to be deleted");
		}
		else{
			parent = current;
			if(current.left.data == num){
				System.out.println("Parent node:" + current.data +"    Left Child node:" + current.left.data);				
				child = current.left;
				flag= true;
				}
			else{
				System.out.println("Parent node:" + current.data +"    Right Child node:" + current.right.data);
				child = current.right;
				flag = false;
			}
			if((child.left==null) && (child.right==null)){ 
				if (flag) parent.left = null;
				else parent.right = null;
			}
			else{
				if(child.right==null){
					if (flag) parent.left = child.left;
					else parent.right = child.left;
				}
				else{
					TreeNode temp = findMin(child.right);
					child.data = temp.data;
					// TODO
					
										
				}
			}
		
		}
		
	}
	public void inorderTraversal(){
		inorderRecur(root);
	}
	private void inorderRecur(TreeNode current) {
		if (current==null)return;
		inorderRecur(current.left);
		System.out.print(current.data+" -->");
		inorderRecur(current.right);
	}
	
	public void preorderTraversal(){
		preorderRecur(root);
	}
	private void preorderRecur(TreeNode current) {
		if (current==null)return;
		System.out.print(current.data+" -->");
		preorderRecur(current.left);		
		preorderRecur(current.right);
	}
	
	public void postorderTraversal(){
		postorderRecur(root);
	}
	private void postorderRecur(TreeNode current) {
		if (current==null)return;
		postorderRecur(current.left);
		postorderRecur(current.right);
		System.out.print(current.data+" -->");
	}
	
}


public class TreeTest {

	public static void main(String[] args) {
		Tree newTree = new Tree();
		for(int i =1;i<=8 ; i++){
			int num = Input.getIntInput();		
			newTree.insert(num);
		}
		
		System.out.println("Inorder Traversal:");
		newTree.inorderTraversal();
		/*
		System.out.println("Pre order Traversal:");
		newTree.preorderTraversal();
		
		System.out.println("PostOrder Traversal:");
		newTree.postorderTraversal();*/
		
		System.out.println("Enter Number to Delete");
		newTree.delete(Input.getIntInput());
		System.out.println("Enter Number to Delete");
		newTree.delete(Input.getIntInput());
		System.out.println("Enter Number to Delete");
		newTree.delete(Input.getIntInput());
		System.out.println("Enter Number to Delete");
		newTree.delete(Input.getIntInput());
	}

}
